// https://www.lintcode.com/problem/number-of-islands/description

// 法一：UF
// class UnionFind {
//     public:
//         int* father;
//         int count;
//     UnionFind(int n) {
//         father = new int[n];
//         for (int i = 0; i < n; i++) {
//             father[i] = i;
//         }
//         count = n;
//     }
//     int find(int n) {
//         if (father[n] == n) {
//             return n;
//         }
//         return find(father[n]);
//     }
//     void connect(int a, int b)  {
//         int rootA = find(a);
//         int rootB = find(b);
//         if (rootA != rootB) {
//             father[rootA] = rootB;
//             count--;
//         }
//     }
//     int check() {
//         return count;
//     }
// };
// class Solution {
// public:
//     /**
//      * @param grid: a boolean 2D matrix
//      * @return: an integer
//      */
     
//     // Union Find 解法，但是对于每块陆地，只需要检测其右面和下面是否是陆地然后做connect，不需要对左和上再作判断，因为遍历顺序是从上到下，从左到右。


//     int numIslands(vector<vector<bool>> &grid) {
//         if (grid.empty() || grid[0].empty()) {
//             return 0;
//         }
//         int n = grid.size();
//         int m = grid[0].size();
        
//         UnionFind u(n * m);
//         int waterCount = 0;
//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < m; j++) {
//                 if (grid[i][j]) {
//                     if (j + 1 < m && grid[i][j + 1]) {
//                         u.connect(i * m + j, i * m + j + 1);
//                     }
//                     if (i + 1 < n && grid[i + 1][j]) {
//                         u.connect(i * m + j, i * m + j + m);
//                     }
//                 } else {
//                     waterCount++;
//                 }
//             }
//         }
//         return u.check() - waterCount;
//     }
// };

// 法二：BFS
// struct Node
// {
//     int x;
//     int y;
// };
// class Solution {
// public:
//     int numIslands(vector<vector<bool>> &grid) {
//         if (grid.empty() || grid[0].empty()) {
//             return 0;
//         }
//         int dx[4] = {-1, 1, 0, 0}; 
//         int dy[4] = {0, 0, -1, 1};
//         int n = grid.size();
//         int m = grid[0].size();
//         queue<Node> q;
//         // vector<vector<bool>> visited(n, vector<int>(m, false));
//         int cnt = 0;
//         // for (int i = 0; i < n; ++i)
//         // {
//         //     for (int j = 0; j < m; ++j)
//         //     {
//         //         if(grid[i][j])
//         //         {
//         //             Node n = {i, j};
//         //             q.push(n);
//         //             cnt++;
//         //         }
//         //     }
//         // }
//         // // 错的，会重复
//         // while (!q.empty())
//         // {
//         //     Node tmp = q.front();
//         //     q.pop();
//         //     for (int i = 0; i < 4; ++i)
//         //     {
//         //         int nx = tmp.x + dx[i];
//         //         int ny = tmp.y + dy[i];
//         //         // if (grid[nx][ny])
//         //         if (nx > 0 && nx < n && ny > 0 && ny < m && grid[nx][ny])
//         //         {
//         //             Node n = {nx, ny};
//         //             q.push(n);
//         //             grid[nx][ny] == 0;
//         //             cnt--;
//         //         }
//         //     }
//         // }
        
//         for (int i = 0; i < n; ++i)
//         {
//             for (int j = 0; j < m; ++j)
//             {
//                 if(grid[i][j]) //发现1就开始BFS
//                 {
//                     Node node = {i, j};
//                     q.push(node);
//                     // grid[i][j] == 0; //注意:赋值为0；别再出现写成==的情况了！
//                     grid[i][j] = 0; 
//                     while (!q.empty())
//                     {
//                         Node tmp = q.front();
//                         q.pop();
//                         for (int i = 0; i < 4; ++i)
//                         {
//                             int nx = tmp.x + dx[i];
//                             int ny = tmp.y + dy[i];
//                             // if (grid[nx][ny])
//                             // if (nx > 0 && nx < n && ny > 0 && ny < m && grid[nx][ny])
//                             if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny])
//                             {
//                                 node = {nx, ny};
//                                 q.push(node);
//                                 // grid[nx][ny] == 0;
//                                 grid[nx][ny] = 0;
//                             }
//                         }
//                     }
//                     cnt++;
//                 }
//             }
//         }
//         return cnt;
//     }
// };

// 法三：DFS
class Solution {
public:
    void dfs(vector<vector<bool>> &grid, int x, int y) {
        if (x < 0 || x >= grid.size()) return;
        if (y < 0 || y >= grid[0].size()) return;
        if (!grid[x][y]) return;
        grid[x][y] = false;
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
    int numIslands(vector<vector<bool>>& grid) {
        // Write your code here
        if (grid.empty() || grid[0].empty()) return 0;
        int N = grid.size(), M = grid[0].size();
        int cnt = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (grid[i][j]) {
                    dfs(grid, i, j);
                    ++cnt;
                }
            }
        }
        return cnt;
    }
};